package com.agile.leetcode.node.removerepeatnode;

import java.util.HashSet;
import java.util.Set;

/**
 * @Author KD
 * @Date 2021/1/26 14:03
 */
@SuppressWarnings("all")
public class RemoveRepeateNode {
    public static void main(String[] args) {
        ListNode node10=new ListNode(5,null);
        ListNode node9 = new ListNode(9, node10);
        ListNode node7 = new ListNode(7, node9);

        ListNode node5 = new ListNode(5, node7);
        ListNode node3 = new ListNode(3, node5);
        ListNode node1 = new ListNode(1, node3);
        RemoveRepeateNode removeRepeateNode=new RemoveRepeateNode();
        ListNode listNode = removeRepeateNode.removeRepeatNode(node1);
        System.out.println(listNode);
    }
    public ListNode removeRepeatNode(ListNode listNode){
        // 创建哑结点
        ListNode dummy=new ListNode(0,null);
        // 创建指针指向哑结点
        ListNode ptr=dummy;
        // 创建集合存储已经有了的节点
        Set<Integer> set=new HashSet<>(10);
        // 遍历节点
        while (listNode!=null){
            // 拿到值
            int value = listNode.value;
            // 判断集合中是否存在
            if (!set.contains(value)){
                // 加入集合
                set.add(value);
                // 加入指针
                ptr.next=listNode;
                // 指针后移
                ptr=ptr.next;
            }else if (listNode.next==null){
                // 是最后一位
                ptr.next=null;
            }
            // 无论是否存在，原始指针都往后移动
            listNode=listNode.next;
        }
        // help Gc
        set=null;
        return dummy.next;
    }
}

class ListNode {
    int value;
    ListNode next;

    public ListNode(int value, ListNode next) {
        this.value = value;
        this.next = next;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "value=" + value +
                ", next=" + next +
                '}';
    }
}

